{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "*[Lab 3, CS206: Data Structures, Bryn Mawr College. In the following cell, give a hash title and by-line. Then you can remove this cell. This lab is due in one week.]*"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "deletable": false,
    "nbgrader": {
     "checksum": "11602f52fe25f5e421531fe993d637c1",
     "grade": true,
     "grade_id": "title",
     "locked": false,
     "points": 10,
     "solution": true
    }
   },
   "source": [
    "YOUR ANSWER HERE"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Sorted Linked Lists\n",
    "\n",
    "Consider our old friend Node:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "class Node {\n",
    "    double data;\n",
    "    Node next;\n",
    "    \n",
    "    Node(double data) {\n",
    "        this.data = data;\n",
    "    }    \n",
    "}"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "Node node = new Node(23.334);"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "node.data"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Now, let's consider a slightly different LinkedList, a SortedLinkedList. This one has an insert method rather than an append method:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "class SortedLinkedList {\n",
    "    Node head;\n",
    "    \n",
    "    public void insert(Node node) {\n",
    "        if (head == null) {\n",
    "            head = node;\n",
    "        } else if (node.data < head.data) {\n",
    "            // insert here\n",
    "            // NEED SOME CODE\n",
    "        } else { // find where to insert it:\n",
    "            Node current = head;\n",
    "            while (current.next != null) {\n",
    "                if (current.data < node.data) {\n",
    "                    // insert it!\n",
    "                    // NEED SOME CODE\n",
    "                    return;\n",
    "                }\n",
    "            }\n",
    "            // You got here and didn't insert!\n",
    "            // insert it here\n",
    "            // NEED SOME CODE\n",
    "        }\n",
    "    }\n",
    "    \n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The idea is that when you insert a Node, it will put it in sorted order. In the next cell, define the method insert, and test it out to show that it works:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true,
    "deletable": false,
    "nbgrader": {
     "checksum": "38ddd62c7fa4b7a1556d14f8e4c598b8",
     "grade": true,
     "grade_id": "sorted-linked-list",
     "locked": false,
     "points": 50,
     "solution": true
    }
   },
   "outputs": [],
   "source": [
    "# YOUR CODE HERE\n",
    "raise NotImplementedError()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Redefine the `SortedLinkedList` in the next cell, this time adding the method `public boolean find(double value)` that will look through the list and return `true` if the item is in the list, and `false` if it is not. When it finds it (or gives up), it should also print out how many comparisons it took. Test your function many times to see how it works."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true,
    "deletable": false,
    "nbgrader": {
     "checksum": "796283187033975a63006b2b3eb196d5",
     "grade": true,
     "grade_id": "find-linked-list",
     "locked": false,
     "points": 50,
     "solution": true
    }
   },
   "outputs": [],
   "source": [
    "# YOUR CODE HERE\n",
    "raise NotImplementedError()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Sorted Binary Tree\n",
    "\n",
    "Consider these Data Structures together that make a `Binary Tree`:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "class Node {\n",
    "    String data;\n",
    "    Node left;\n",
    "    Node right;\n",
    "}\n",
    "\n",
    "class BinaryTree {\n",
    "    Node head;\n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We want to add an `public void insert(Node node)` method to BinaryTree  like our SortedLinkedList, but we want to BinaryTree to remain sorted such that:\n",
    "\n",
    "* any string in any left branch is less than data\n",
    "* any string in any right branch is >= than data\n",
    "\n",
    "Note that this is a recursive constraint, and is true for all BinaryTrees. Put the String in the first place that it will fit.\n",
    "\n",
    "```java\n",
    "class BinaryTree {\n",
    "    Node head;\n",
    "    \n",
    "    public void insert(Node node) {\n",
    "        /// NEED CODE HERE\n",
    "    }\n",
    "    \n",
    "}\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "In the following cell, define a `BinaryTree` with an `public void insert(Node node)` method. Test it out thoroughly to make sure it works."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true,
    "deletable": false,
    "nbgrader": {
     "checksum": "9f1117c9f41c3ebb2cb858608ebfa5f0",
     "grade": true,
     "grade_id": "binary-tree",
     "locked": false,
     "points": 50,
     "solution": true
    }
   },
   "outputs": [],
   "source": [
    "# YOUR CODE HERE\n",
    "raise NotImplementedError()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "In the next cell, redefine `BinaryTree` to include the method `public boolean find(String value)` to search through and see if that value is in the tree. Return `true` or `false` appropriately. In addition, it should print out how many comparisons it took to determine the answer."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true,
    "deletable": false,
    "nbgrader": {
     "checksum": "28c9969e9092f6487a1c2e7a232d0dd0",
     "grade": true,
     "grade_id": "find-binary-tree",
     "locked": false,
     "points": 50,
     "solution": true
    }
   },
   "outputs": [],
   "source": [
    "# YOUR CODE HERE\n",
    "raise NotImplementedError()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Reflection"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "*[In the following cell, give a thorough reflection of what you found and learned in this lab. Then you can remove this cell.]*"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "deletable": false,
    "nbgrader": {
     "checksum": "fb5a1fdd7fbc9cd9dd47331cfbd26d67",
     "grade": true,
     "grade_id": "reflection",
     "locked": false,
     "points": 50,
     "solution": true
    }
   },
   "source": [
    "YOUR ANSWER HERE"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Java 9",
   "language": "java",
   "name": "java9"
  },
  "language_info": {
   "file_extension": ".class",
   "mimetype": "application/java-vm",
   "name": "java"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 0
}